1. Field of the Invention
This invention relates to a method and device for electronic data processing, particularly in the field of financial informatics. More particularly, this invention relates to fast and accurate valuation of financial derivatives using electronic computer systems.
2. Description of Related Art
The valuation of financial derivatives has become popular in the last decade and has become an important instrument in financial economics. The possibility of such valuation is a necessary prerequisite for a financial institution to be able to offer a new derivative. Also, this valuation is necessary in order to structure, collateralize, and optimize a financial portfolio.
There are many different kinds of financial derivatives, such as those based on interest rates and/or assets. This includes, among others, bonds, swaps, future, CMOs, and options. Their valuation occurs under the assumption of the arbitrage principle using partial differential equations or the martingale approach. The martingale is more general, where a stochastic process for an underlying value, such as an interest rate or asset price, is first specified. Then, the equivalent martingale measure which converts the underlying process into a martingale is determined. Finally, the value of the derivative is computed as the expectation of its discounted payoff function under this risk-neutral measure. Under certain conditions the approaches via partial differential equations and martingales are equivalent. The connection is made by generalized Feynman-Kacz formulas. However, the martingale approach is more universal and easier to adapt to new situations.
The price of a financial derivative can thus be expressed as an expectation. In continuous time, the integrand itself contains a path integral, which can be discretized with the Euler method/trapezoidal rule or similar methods. Sometimes, induced by the application, a time-discrete model is used. Both cases lead to high-dimensional integration problems. For the simple European call option it is possible to give a closed-form solution, a Black-Scholes formula, but more complex options require a numerical solution method. This holds for other types of financial derivatives analogously.
Classical multivariate quadrature is not suited as a numerical integration method for high-dimensional integrands. Problems associated with dimension are encountered because the work scales exponentially with the dimension. The complexity is of the order O (N−r/d) where r is the smoothness of the integrand and d its dimension. On the other hand, the Monte Carlo method is independent of the dimension. Here, the integrand ƒ is evaluated at a random series of N points xi which results in the following quadrature formula.
                                          Q            N                    ⁢          f                =                              1            N                    ⁢                                    ∑                              i                =                1                            N                        ⁢                          f              ⁡                              (                                  x                  i                                )                                                                        Equation        ⁢                                  ⁢        1            
The Monte Carlo methods converges very slowly and only in a stochastic sense. The accuracy which can be reached with N function evaluations is of the order O (1/√N). With Quasi-Monte Carlo methods which have been developed in the last decade, the integrand is evaluated at a deterministically determined series of points xi and in analogy to the Monte Carlo method, the following quadrature formula is used.
                                          Q            N                    ⁢          f                =                              1            N                    ⁢                                    ∑                              i                =                1                            N                        ⁢                          f              ⁡                              (                                  x                  i                                )                                                                        Equation        ⁢                                  ⁢        2            
There is a variety of different constructions, for example the Halton, Sobol sequences or Faure sequences, which differ in corresponding pre-asymptotic behavior and all have an order of convergence of O ((log N)d/N). In addition the error is deterministic. Prototype is the program FinDer of J. Traub, S. Paskov, Faster evaluation of financial derivatives, Journal of Portfolio Management 22, 1, 113-120 (1995), which is used by many banks. This method is disclosed by U.S. Pat. Nos. 5,940,810 and 6,058,377.
On the other hand, the so-called sparse grid method is an approach where multivariate quadrature formulas are constructed by suitable combination of tensor products of univariate quadrature formulas, such as the Clenshaw-Curtis or Gauss-Patterson formulas.
The general sparse grid methods can be described as follows. Consider a series of univariate quadrature formulas for a univariate function ƒ, represented by the following formula.
                                          Q            l            1                    ⁢          f                :=                              ∑                          i              =              1                                      n              l              1                                ⁢                                    w              li                        ·                          f              ⁡                              (                                  χ                  li                                )                                                                        Equation        ⁢                                  ⁢        3            
Now, define the difference formula byΔk1ƒ:=(Qk1−Qk−11)ƒ withQ01ƒ:=0  Equation 4
The sparse grid construction for d-dimensional functions ƒ consists for lεIN and kεINd of
                                          Q            l            d                    ⁢          f                :=                              ∑                          k              ∈                              I                l                                              ⁢                                    (                                                Δ                                      k                    1                                    1                                ⊗                …                ⊗                                  Δ                                      k                    d                                    1                                            )                        ⁢            f                                              Equation        ⁢                                  ⁢        5            with index sets Il such that the following function holds for all kεIlk−ejεIl for 1≦j≦d, kj>1  Equation6
Special cases of the method are classical sparse grids, where Il={|k|1≦l+d−1}, as well as classical product formulas where Il={|k|∞≦l }. FIG. 4 shows examples of three different classical sparse grids in the 2D case based on the trapezoidal rule, the Clenshaw-Curtis formula, the Gauss-Patterson formula, and the Gauss-Legendre formula.
One substantial difference to Monte Carlo and Quasi-Monte Carlo methods is the use of weight factors of different size. Now, in the representation QNƒ=Σi=1Nwiƒ(xi), the weights wi of the sparse grid method are not all equal to 1/N.
The order of convergence of the classical sparse grid method is ε=O(log(N)(d−1)(r+1) N−r) and thus it is also independent of the dimension d. In contrast to Monte Carlo and Quasi-Monte Carlo methods, the sparse grid method is able to use the smoothness r of the integrand and thus has exponential convergence for smooth integrands (r?∞). Thus, for smooth integrands this method is substantially faster than the Monte Carlo or Quasi-Monte Carlo methods.
For the sparse grid method, one problem is that the convergence rate deteriorates for non-smooth integrands which show up for options, and its advantage is thus lost. Another problem is that the method is, just as the Quasi-Monte Carlo method, not entirely independent of the dimension, and the rate of convergence also degrades with rising dimension.